☝ La réciproque est fausse - Remarque

Supposons que \(n^{p-1} \equiv 1 \ [p]\) pour tout \(n \in \mathbb{Z}\) tel que \(p\) est premier avec  \(n\) : peut-on en déduire que \(p\) est premier ? Cela signifierait que la réciproque du petit théorème de Fermat est vraie... mais ce n'est pas le cas !

Exemple

On considère le nombre \(p=561=3 \times 11 \times 17\)  qui n'est clairement pas un nombre premier !

Soit \(n \in \mathbb{Z}\) un entier qui est premier avec  \(561\) . Par conséquent, \(n\) n'est divisible ni par \(3\) , ni par \(11\) , ni par \(17\)  (sinon il ne serait pas premier avec  \(561\)  !).

Comme \(3\) , \(11\) et \(17\) sont premiers, d'après le petit théorème de Fermat (forme forte), on a :

• \(n^2 \equiv 1 \ [3]\) , donc \((n^2)^{280} \equiv 1^{280} \ [3]\) , c'est-à-dire \(n^{560} \equiv 1 \ [3]\) ;
• \(n^{10} \equiv 1 \ [11]\) , donc \((n^{10})^{56} \equiv 1^{56} \ [11]\) , c'est-à-dire \(n^{560} \equiv 1 \ [11]\) ;
• \(n^{16} \equiv 1 \ [17]\) , donc \((n^{16})^{35} \equiv 1^{35} \ [17]\) , c'est-à-dire \(n^{560} \equiv 1 \ [17]\) .

On en déduit que \(n^{560}-1\) est divisible par \(3\) et par \(11\) , qui sont premiers entre eux, donc, d'après le corollaire du théorème de Gauss, \(n^{560}-1\) est divisible par \(3 \times 11=33\) .

Ensuite, \(n^{560}-1\) est divisible par \(33\) et par \(17\) , qui sont premiers entre eux, donc, d'après le corollaire du théorème de Gauss, \(n^{560}-1\) est divisible par \(33 \times 17=561\) .

On a donc \(n^{560} \equiv 1 \ [561]\) , avec \(561\) qui ne divise pas \(n\) , et pourtant, \(561\) n'est pas premier.